package 每日一题;

import com.alibaba.fastjson.JSON;

import java.util.*;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-27
 **/

public class No301删除无效的括号 {

    /**
     * 给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
     * 返回所有可能的结果。答案可以按 任意顺序 返回。
     * <p>
     * 示例 1：
     * 输入：s = "()())()"
     * 输出：["(())()","()()()"]
     * 示例 2：
     * 输入：s = "(a)())()"
     * 输出：["(a())()","(a)()()"]
     * 示例 3：
     * 输入：s = ")("
     * 输出：[""]
     *  
     * 提示：
     * 1 <= s.length <= 25
     * s 由小写英文字母以及括号 '(' 和 ')' 组成
     * s 中至多含 20 个括号
     */

    public List<String> removeInvalidParentheses(String s) {

        /**
         * 暴力暴力,对原字符进行sub,循环的每次仅sub掉一个符号,然后将字符串加入集合中,
         * 每次开始前就对集合中的字符串进行有效括号判断,有一层成功了,那么就带着这层的答案,在这层return结果
         */
        Set<String> result = new HashSet<>();
        Deque<String> queue = new ArrayDeque<>();
        // 不可重复放入队列
        Set<String> set = new HashSet<>();
        queue.addLast(s);
        set.add(s);
        set.add("");

        while (!queue.isEmpty()) {

            int count = queue.size();


            while (count > 0) {

                String itemS = queue.removeFirst();

                if (this.valid(itemS)) {
                    result.add(itemS);
                    count--;
                    continue;
                }

                // 重新放入
                for (int i = 0; i < itemS.length(); i++) {

                    // 这里应该需要删除多一点

                    if (itemS.charAt(i) == '(' || itemS.charAt(i) == ')') {
                        // 截取后放入
                        String str = itemS.substring(0, i) + itemS.substring(i + 1);
                        if (!set.contains(str)) {
                            set.add(str);
                            queue.addLast(str);
                        }
                    }

                }

                count--;
            }

            if (result.size() != 0) {
                return new ArrayList<>(result);
            }

        }


        return new ArrayList<>(Arrays.asList(""));
    }

    private boolean valid(String str) {
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == '(') {
                count++;
            }
            if (c == ')') {
                count--;
            }
            if (count < 0 || count > str.length() - i + 1) {
                return false;
            }
        }
        return count == 0;
    }

    public static void main(String[] args) {
        No301删除无效的括号 n = new No301删除无效的括号();
        List<String> result = n.removeInvalidParentheses("()(((((((()");
        System.out.println(JSON.toJSONString(result));
    }

}
